1. Field of the Invention
The present invention relates generally to data processing devices, and more particularly, to systems and methods for preserving the order of data processed by multiple processing paths in data processing devices.
2. Description of Related Art
In network devices that must deliver high throughput in forwarding a stream of data, a conventional approach is to provide n independent paths and distribute sub-streams of the data down each of the n paths. After processing by each of the n processing paths, the sub-streams are recombined to create an output stream. A problem that arises using this technique is that the different processing paths may have different delays. As a result, if a first block of data (e.g., a packet or cell) is sent down a first path at time t1 and a second block of data is sent down a second path at time t2>t1, the second block of data may nonetheless finish being processed before the first. Therefore, if nothing is done to correct for this differential delay, the recombined stream of data will be out-of-order relative to the input stream. Out-of-order blocks of data can be problematic in a number of networking applications.
There are well-known algorithms for restoring order to mis-ordered streams at recombination time, based on attaching sequence numbers to consecutive blocks at input, and sorting blocks to restore consecutive sequence numbers on output. However, in some applications, a given output will not receive all sequence numbers from a given input, making the standard sorting algorithms impractical.
Therefore, there exists a need for systems and methods that can preserve the order of blocks of data in data streams that have been distributed across multiple paths in a network device.